1. Field of the Invention
The present invention relates to a data transferring method, and in particular to a data transferring method in case of transmitting data to a plurality of terminals over a network.
In recent years, various services have been remarkable utilizing networks such as the Internet or intranet. As an example, are taken services which utilize those networks to distribute images or voice data. In these services, users can freely access to watch the images or listen to the voice data saved in servers.
These services are usually performed by a data transferring method which is called a unicast in which data are transmitted individually, that is one to one. Also, there are services in which data are transmitted simultaneously to users, e.g. by a multicast.
Hereinafter, the operations of the unicast and the multicast will be described referring to FIGS. 17 and 18, respectively.
(1) Unicast: see FIG. 17
The data transmission is performed one to one in the unicast. Namely, as shown in FIG. 17, a server S1 which is on a transmitting side transmits data with a proper address xe2x80x9c192.168.100.201xe2x80x9d of a terminal C1 as a destination address. Then the data will be transmitted to the terminal C1 which is the destination.
(2) Multicast: see FIG. 18
A multicast address is prepared for each service in the multicast. For example, an address xe2x80x9c224.1.1.100xe2x80x9d is prepared for sports programs. Users who wish to have this service can receive the data by joining the multicast address xe2x80x9c224.1.1.100xe2x80x9d.
The server which is on a transmitting side only has to transmit data to the address xe2x80x9c224.1.1.100xe2x80x9d as in the case of unicast. Then, copies of data are made as required in the process of data transmission, so that the data are finally sent to all of the terminals (C1 and C4) which have requested to receive.
In the multicast, since the data transmission by the server can be performed once no matter how many terminals there are to receive the data, it is characterized that loads of the network and the servers are reduced.
Therefore, the multicast is expected to have a large effect upon transmitting image data, such as relaying sports, events, or lecture images in a broadcast-like service form, which give heavy loads on the network and the servers.
However, there is no mechanism for guaranteeing data arrivals in the multicast. In other words, the server transmits data one-sidedly without taking any measures even if the data get lost on the way.
Also, when there is a difference between the rate in which receiving terminals consume the images or the voice data and the transmission rate of the server, it is possible for buffers in the receiving terminals to undertow or overflow.
From this point of view, a resending control for compensating the lost data (packets) when distributing data over the network and a flow control for controlling buffers in the receiving terminals not to overflow or underflow are required.
2. Description of the Related Art
(1) Prior Art Related to Resending Control
Firstly, a transmitting terminal (e.g., a server) embeds sequential numbers into transmitting packets. Receiving terminals (clients) can detect lost packets by checking the sequential numbers. The receiving terminals which have detected the lost packets request the transmitting terminal to resend the data, which will be compensated by having the transmitting terminal resend the requested data.
(2) Prior Art Related to Flow Control
{circle around (1)} Fixed Rate Control
Since the consumption rate of data is preliminarily determined for the images and the voice data, the transmitting terminal keeps sending the data at the same rate. Taking an example of 6 Mbps images data, the transmitting terminal transmits the data at the rate of 6 Mbps.
{circle around (2)} Window Control
This is a method by which the receiving terminals notify the receipt of data as well as their remaining buffer quantities to the transmitting terminal every time the receiving terminals receive the data.
The transmitting terminal transmits data based on empty buffer quantities of the receiving terminals. If there is an empty buffer of 100 KB in a receiving terminal, the transmitting terminal transmits 100 KB data, which is similarly repeated as shown in FIG. 19 (a method used in TCP).
{circle around (3)} ACK Base Control
Firstly, the transmitting terminal transmits data at a fixed rate as shown in FIG. 20. The transmission rate of the transmitting terminal is preset a little higher than the actual consumption rate of the images or the voice data. Then the data will accumulate in the buffer of the receiving terminal. When the receiving terminal detects that the buffer is about to overflow, the receiving terminal transmits a packet (ACK packet) indicating that the buffer is overflowing to the transmitting terminal. The transmitting terminal which has received this packet stops the transmission for a fixed period of time, thereby suppressing the buffer overflow in the receiving terminal.
(1) Problems Related to Resending Control
The above-mentioned prior art of the resending control has no problem as for a unicast data transfer. However, as for the multicast, since the number of the receiving terminals cannot be specified, there is a possibility that a large number of resending request packets are generated (see FIG. 21). In this case, not only the resending process but also other data transfer processes are disabled, resulting in harmful influences over the entire network.
(2) Problems Related to Flow Control
The problem related to the above-mentioned fixed rate control {circle around (1)} is that even if the transmission rate of the transmitting terminal is fixed, a buffer failure of the receiving terminal may occur in the course of the continuous transmission (see FIG. 22). This is caused by a little difference between the clock timings of the transmitting terminal and the receiving terminal. For example, the buffer failure occurs when the clock on the transmitting terminal side indicates that one hour has elapsed whereas the clock on the receiving terminal side indicate that only 59 minutes and 59 seconds have elapsed. This kind of difference occurs similarly in case of multicast for each terminal (see FIG. 23).
As for common problems between the above-mentioned window control {circle around (2)} and ACK base control {circle around (3)}, the following three points are cited:
(i) Utilization for Multicast not Being Considered
Regarding the window control {circle around (2)}, when different quantities of empty buffers are notified from the receiving terminals, it is difficult to determine how much data to transmit. Regarding the ACK base control {circle around (3)}, only the receiving terminal which has the buffer occupied finally with the largest quantity is to be controlled so that the other receiving terminals are not considered.
(ii) Weakness for Network Delay
Regarding the window control {circle around (2)}, unless a packet from the receiving terminal which notifies the empty space of the buffer arrives at the transmitting terminal, the transmitting terminal cannot transmit the next data. Therefore, a throughput performance decreases in a network with a large delay.
Regarding the ACK base control {circle around (3)}, there is a possibility in a network with a large delay that the buffers of the receiving terminals fail before the ACK packets from the receiving terminals reach the transmitting terminal to effect the stop of transmission.
Namely, both control methods {circle around (2)} and {circle around (3)} are unsuitable for the utilization in a large-scaled network.
(iii) Increase of Transmission Packets
Regarding the window control {circle around (2)}, since the flow is to have the receiving terminals notify empty buffers and then to have the transmitting terminal transmit the data, there is a proportional relationship between the numbers of transmitting packets and control packets.
Regarding the ACK base control {circle around (3)}, although it depends on the transmission rates or the stop period after receiving the ACK packet, there is a proportional relationship between the numbers of transmitting packets and control packets.
Namely, as the number of the transmitting packets increases, the number of the control packets increases as well, resulting in plenty of packets for the flow control flowing over the network.
It is accordingly an object of the present invention to provide a data transferring method comprising a resending control step and a flow control step which reduce a load of network and avoid buffer failures at receiving terminals as much as possible.
[1] A data transferring method according to the present invention for the achievement of the above-mentioned object comprises a local resending control step for multicasting resending requests and resending data from predetermined terminals within the same subnet, and a global resending control step for unicasting resending requests and resending data from terminals other than the predetermined terminals to terminals located outside of the subnet.
Namely, in the local resending control step, as schematically shown in FIG. 1, when a predetermined terminal C1 within a subnet SN1 detects a packet loss in the received data, the terminal C1 transmits a resending request {circle around (1)} within the same subnet SN1 in the form of a multicast packet.
A terminal C3 within the subnet SN1 which receives the resending request {circle around (1)} and has the packet as requested resends the packet {circle around (2)} within the subnet SN1 by multicast.
In the global resending control step, as schematically shown in FIG. 2, a terminal C4, for example, other than the predetermined terminals within the same subnet SN1 transmits a resending request to a terminal T1 located outside of the subnet SN1. At this time, the terminal C4 establishes a connection in advance (e.g., though a router R) with the destination terminal T1 to which the resending request is transmitted. In response to a resending request {circle around (3)}, resending data {circle around (4)} are transmitted from the destination terminal T1 by unicast.
Thus, the local resending control can restrict packet losses proper to the terminals to a limited area which is the subnet. If there are some terminals which have the same data within the subnet, the resending operation can be completed by exchanging a request packet and a resending packet within the subnet, thereby enabling a great reduction of the loads on the servers or the network.
In the global resending control step, by a unicast request of resending a packet lost in common to all of the terminals within the subnet such as a packet lost at a router, unnecessary transmisison of data to the entire network can be avoided. Also, not only a server but also a terminal located outside of the subnet can receive the global resending request as a destination, so that the loads of the servers can be reduced, enabling the application for a large-scaled network.
[2] In the above mentioned invention [1], the multicasting step may be executed under the condition that when it is detected that other terminals within the same subnet have transmitted at least one of the resending requests and the resending data, the predetermined terminals stop the transmission of at least one of the resending requests and the resending data.
Namely, the number of transferring packets can be suppressed by performing the local resending control by multicast under a predetermined condition that the terminals stop the transmission when it is detected that another terminal within the subnet has transmitted the resending request or the resending data in advance.
[3] In the above mentioned invention [1], the unicasting step may be executed with a connection established fixedly in advance.
Namely, by this method, regardless of the presence of the data to be transmitted, the terminal which transmits resending requests and the terminal which receives the resending request mutually inform of their own addresses in advance whereby the connection is always established. This is effective in the case where the network configuration does not change.
Thus, by always establishing the connection, an immediate resending control can be performed as required without taking time to establish the connection.
[4] In the above mentioned invention [1], an address of a connection used for the unicasting step may be different from an address used for data transmission.
This is effective when the connection is dynamically established between the terminal which transmits the resending request and the terminal which receives the resending request. In this case, the terminal which receives the resending request transmits, for example, a packet for inviting a connection to the network by multicast. Any terminal wishing to establish a connection can establish the connection by applying for the connection inviting packet.
In case the invitation and the application for the connection are performed by using the address used for the data transmission, if data other than the connection inviting packet are being transmitted (from server and the like) to the address used for the data transmission at the time when the terminal wishing to establish the connection tries to receive the connection inviting packet with the address used for the data transmission, the terminal will receive those data. Namely, there is a possibility that the terminal even receives unnecessary data.
Therefore, by using different addresses for the connection control and for the data transmission, such unnecessary data can be prevented from being transmitted to the terminal.
[5] In the above mentioned invention [1], the terminals located outside of the subnet may comprise servers.
[6] In the above mentioned invention [5], the method may further comprise a flow control step for destination terminals to secure necessary buffer quantities according to transmission rates and service times of data transmitted by the servers. (This method is hereinafter occasionally referred to as xe2x80x9cvariable buffer methodxe2x80x9d.)
Namely, each terminal inquires the server of rates and the service times of the transmitting data before starting the service as shown in FIG. 3. Each terminal avoids a buffer failure by considering an expected clock difference which is recognized by its own terminal in addition to the rates and the service times of the transmitting data to calculate and secure the required buffer quantity.
For example, it is assumed that the clock difference is xc2x1100 ppm. In order to reproduce the images which have a data rate of 6 Mbps for two hours, the required buffer quantity is given by:       2    xc3x97                            100          _                xc3x97                  10                      -            6                                                ↑                      xe2x80x83                    ⁢          100                ⁢                  xe2x80x83                ⁢        ppm              xc3x97                            6          _                xc3x97                  10          6                xc3x97                              ↑                      xe2x80x83                    ⁢          6                ⁢                  xe2x80x83                ⁢        Mbps              ⁢                                        2            xc3x97            60            xc3x97            60                    _                ÷                              ↑                      xe2x80x83                    ⁢          2                ⁢                  xe2x80x83                ⁢        hours              ⁢    8    =      1080000    ⁢          xe2x80x83        ⁢          (      bytes      )      
Thus, the required buffer quantity can be determined if the expected clock difference, the data rate, and the reproduction time are given. Since each terminal secures the above-mentioned buffer quantity, useless buffers can be removed, thereby enabling an efficient utilization of memories.
[7] In the above mentioned invention [5], the method may further comprise a flow control step wherein the servers change transmission rates based on notifications of buffer quantities from destination terminals. (This method is hereinafter occasionally referred to as xe2x80x9cvariable transmission rate methodxe2x80x9d.)
Namely, while transmitting the data at a fixed rate (e.g., 6 Mbps), the server periodically inquires the terminals of the buffer states to change the transmission rate based on the buffer quantity notifications from the terminals (see FIG. 4). This rate determination procedure will now be described by illustrating the case of unicast referring to FIG. 5.
Buffer quantities measured before and after an interval Txe2x80x2 are supposed to be bxe2x80x2 and b, respectively. Also, a transmission rate during the interval is supposed to be Rxe2x80x2 and a target buffer quantity is supposed to be xcex2 A difference between the current buffer quantity b and the target buffer quantity xcex2 is defined as xcex94xcex2(=xcex2xe2x88x92b). A transmission rate R during the next interval T is determined by the following equation:                               R          =                                    R              xe2x80x2                        +                                          p                                                      xe2x80x83                                    ↑                                            ⁢                                                Δ                  ⁢                                      xe2x80x83                                    ⁢                  β                                T                                      -                          q              ⁢                              xe2x80x83                            ⁢                                                                                          xe2x80x83                                        ⁢                                          (                                              b                        -                                                  b                          xe2x80x2                                                                    )                                                                            T                    xe2x80x2                                                  ↑                                                    ⁢                  
                ⁢                  xe2x80x83                ⁢                  1          ⁢          st          ⁢                      xe2x80x83                    ⁢          member          ⁢                      xe2x80x83                    ⁢          2          ⁢          nd          ⁢                      xe2x80x83                    ⁢          member                                    Eq        .                  xe2x80x83                ⁢                  (          1          )                    
where p and q are arbitrary parameters which take values between 0 and 1. The first member of Eq. (1) is an item for making the buffer approach the target value. In other words, since the difference between the target buffer quantity and the present buffer quantity is xcex94xcex2, an item xcex94xcex2/T indicates a rate required for filling the difference xcex94xcex2 within the next T seconds. On the other hand, the second member indicates a power for stabilizing the buffer. Since the buffer has changed from bxe2x80x2 to b in Txe2x80x2 seconds, only (bxe2x88x92bxe2x80x2)/Txe2x80x2 can be subtracted from the rate in order to cancel the change.
It is to be noted that the characteristic of the rate correction can be changed by varying p and q. When p is large, the convergence to the target value becomes fast, however the stability of the rate is correspondingly weakened. When q is large, the buffer is stabilized, however the convergence to the target value takes time. Therefore, p and q are determined in accordance with the environment to be utilized.
[8] In the above mentioned invention [7], the flow control step may include a step for the servers to multicast requests for notification of buffer quantities and for each terminal to unicast the notification.
Namely, when the server transmits data by multicast, the server requests all of the object terminals by multicast to notify the buffer quantities. The terminals notify the buffer quantities in response to the requests. At this time, the load of the network can be reduced by unicasting the notification.
It is to be noted that when multicasting the notification requests to the terminals, the server adjusts the rate in the above-mentioned invention [7] by taking the proportion of the transmission data occupying the total buffer of the terminals as the target for rate setting.
It is supposed that a notified total buffer quantity of the n-th terminal is Bn and the amount of data within the buffer is bn (see FIG. 6). Also, the buffer quantity of the terminal is supposed to have increased by xcex94xcex2 depending on the transmission rate of the server. The average buffer usage rate w at this point can be expressed as follows:                     w        =                                            1              N                        ⁢                                          ∑                                  n                  =                  1                                N                            ⁢                              xe2x80x83                            ⁢                                                (                                                            b                      n                                        +                                          Δ                      ⁢                                              xe2x80x83                                            ⁢                      β                                                        )                                                  B                  n                                                              =                                    1              N                        ⁡                          [                                                Δ                  ⁢                                      xe2x80x83                                    ⁢                  β                  ⁢                                                            ∑                                              n                        =                        1                                            N                                        ⁢                                          xe2x80x83                                        ⁢                                          1                                              B                        n                                                                                            +                                                      ∑                                          n                      =                      1                                        N                                    ⁢                                      xe2x80x83                                    ⁢                                                            b                      n                                                              B                      n                                                                                  ]                                                          Eq        .                  xe2x80x83                ⁢                  (          2          )                    
From Eq. (2) above, xcex94xcex2 can be given by the following equation.                               Δ          ⁢                      xe2x80x83                    ⁢          β                =                              [                          wN              -                                                ∑                                      n                    =                    1                                    N                                ⁢                                  xe2x80x83                                ⁢                                                      b                    n                                                        B                    n                                                                        ]                                              ∑                              n                =                1                            N                        ⁢                          xe2x80x83                        ⁢                          1                              B                n                                                                        Eq        .                  xe2x80x83                ⁢                  (          3          )                    
For example, it should be set that w=0.5 in order to adjust the rate so that the buffers of the terminals may be half filled.
xcex94xcex2 is calculated from Eq. (3) and the transmission rate is calculated from Eq. (1), based on the notifications from the terminals. [9] [10] In the above mentioned invention [6] or [8], the flow control step may include a step for dividing the destination terminals into groups according to the buffer quantities, one group of the terminals tending to overflow, the other group of the terminals tending to underflow, and for transmitting the data with a plurality of transmission rates suitable respectively for the groups.
Namely, in the variable transmission rate method, the server divides the terminals into two groups according to the buffer quantities notified by the destination terminals; one group of the terminals tending to overflow; the other group of the terminals tending to underflow. Then the server separately multicasts the transmitting data to each group of the terminals at the transmission rate corresponding to the average buffer quantity of each group.
Moreover, in the variable buffer method, the data transmission is performed by using a new transmission rate when it becomes necessary to perform services longer in time than expected.
Although the loads of the servers and the network increase with a plurality of transmission rates, the time before the buffer failures occur in the destination terminals can be extended.
[11] In the above mentioned invention [5], the method may further comprise a flow control step for the destination terminals which receive the data from the servers to synchronize their own clocks with the clocks of the servers (clock synchronization method).
Namely, this invention resides in adjusting the clock timings of the terminals to those of the server. The server sends a xe2x80x9csynchronization packetxe2x80x9d to the object terminals at certain intervals which may not necessarily be fixed. The present time of the server itself (or the elapsed time after the initiation) is embedded into this packet. It is alternatively possible to embed the time of the server in the data packets.
The terminals which have received this packet record the times of their own when they did so as well as the time of the server itself (or the elapsed time after the initiation). This operation can be repeated several times and plotted as shown in FIG. 7.
A linear approximation of these plots can be obtained by applying the least squares method or the like, as follows:
Ts=aTc+bxe2x80x83xe2x80x83Eq. (4)
where Ts is the time of the server and Tc is the time of terminals. xe2x80x9caxe2x80x9d in the above equation indicates how different the clocks of the server and the terminal gain.
When the images or the voice data are decoded on the terminal side, the time given by the above-mentioned Eq. (4) according to the time received from the server is determinded for use.
[12] In the above mentioned invention [11], the flow control step may include a step for destination terminals to preliminarily synchronize the clocks before services.
Namely, the server transmits the above-mentioned xe2x80x9csynchronization packetxe2x80x9d irrespective of the presence of the service, whereby the terminals can preliminarily synchronize the clocks before the initiation of the service. As a result, the clock differences immediately after the initiation of the service become small.
[13] In the above mentioned invention [12], the step for preliminarily synchronizing the clocks may include a step for the servers to notify a time notification packet from the same servers to the destination terminals using an address different from data transmission address.
Namely, the server transmits the above-mentioned xe2x80x9csynchronization packetxe2x80x9d by using the address different from the data transmission address. As a result, superfluous data can be prevented from being transmitted to terminals or a network which are out of the service.